package com.cande.loki.exercise.algorithm;

import java.util.LinkedList;

/**
 * 树结构
 * https://zhuanlan.zhihu.com/p/272791799
 */
public class Tree {

    public static void main(String[] args) {
        Node root = new Node("1");
        Node node2 = new Node("2");
        Node node3 = new Node("3");
        Node node4 = new Node("4");
        Node node5 = new Node("5");
        Node node6 = new Node("6");
        Node node7 = new Node("7");
        Node node8 = new Node("8");
        root.setLeft(node2);
        node2.setLeft(node4);
        node5.setLeft(node7);
        root.setRight(node3);
        node3.setRight(node6);
        node2.setRight(node5);
        node5.setRight(node8);

        pre(root);
        System.out.println("--------");
        mid(root);
        System.out.println("--------");
        last(root);
        System.out.println("--------");
        bfs(root);
//              1
//           2     3
//         4   5     6
//            7  8
    }

    //前序 根 左 右
    public static void pre(Node root){
        if (root != null) {
            System.out.println(root.data);
            pre(root.left);
            pre(root.right);
        }

    }
    //中序 左 根 右
    public static void mid(Node root){
        if (root != null) {
            mid(root.left);
            System.out.println(root.data);
            mid(root.right);
        }
    }

    //后序 左 右 根
    public static void last(Node root){
        if (root != null) {
            last(root.left);
            last(root.right);
            System.out.println(root.data);
        }
    }
    //层次遍历
    public static void bfs(Node root) {
        if (root == null) {
            return;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node node = queue.pop();
            System.out.println(node.data);
            if (node.getLeft() != null){
                queue.offer(node.getLeft());
            }
            if (node.getRight() != null){
                queue.offer(node.getRight());
            }
        }
    }

    static class Node{
        String data;
        Node left;
        Node right;

        public Node(String number) {
            data = number;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }
}
